from typing import List

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        result = []
        n = len(graph)

        def backtrack(node: int, path: List[int]):
            if node == n - 1:
                result.append(list(path))  # 保存当前路径的一个副本
                return

            for neighbor in graph[node]:
                path.append(neighbor)
                backtrack(neighbor, path)
                path.pop()  # 回溯，移除当前路径末尾

        # 初始路径为 [0]
        backtrack(0, [0])
        return result

# 示例输入
graph1 = [[1,2], [2,3], [3], []]
graph2=[[4,3,1],[3,2,4],[3],[4],[]]
# 创建 Solution 实例
sol = Solution()

# 调用方法并获取结果
paths1 = sol.allPathsSourceTarget(graph1)
paths2 = sol.allPathsSourceTarget(graph2)
# 打印结果
print("graph1中所有从节点 0 到节点 n-1 的路径：")
for path in paths1:
    print(path)


print("graph2中所有从节点 0 到节点 n-1 的路径：")
for path in paths2:
    print(path)
